package leetcode.tree.binary.traversal;

import leetcode.tree.binary.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 145. 二叉树的后序遍历
 */
public class PostOrderTraversal {

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        // 构建二叉排序树(完全二叉树)
        TreeNode tree = TreeNode.createTreeByArr(arr);

        PostOrderTraversal solution = new PostOrderTraversal();
        // 后序遍历  8, 4, 5, 2, 6, 7, 3, 1
        List<Integer> resList = solution.postOrderTraversal2(tree);
        System.out.println(resList);
    }

    /**
     * 递归实现
     * @param root
     * @return
     */
    public List<Integer> postOrderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postOrder(root, res);
        return res;
    }

    public void postOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postOrder(root.left, res);
        postOrder(root.right, res);
        res.add(root.val);
    }


    /**
     * 栈实现
     *
     * @param root
     * @return
     */
    public List<Integer> postOrderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        // 主要思想：
        // 由于在某颗子树访问完成以后，接着就要回溯到其父节点去
        // 因此可以用prev来记录访问历史，在回溯到父节点时，可以由此来判断，上一个访问的节点是否为右子树
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 从栈中弹出的元素，左子树一定是访问完了的
            root = stack.pop();
            // 现在需要确定的是是否有右子树，或者右子树是否访问过
            // 如果没有右子树，或者右子树访问完了，也就是上一个访问的节点是右子节点时
            // 说明可以访问当前节点
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                // 更新历史访问记录，这样回溯的时候父节点可以由此判断右子树是否访问完成
                // 只要进行访问节点, 保存遍历结果, 就立刻把prev指向保存的节点, 所以prev始终指向上一个访问的节点
                prev = root;
                // 避免重复访问左子树[设空节点]
                // 这边当前指针一定置空, 否则再次进入while循环又会不断遍历左子树, 陷入死循环
                // 置空之后, root从栈中取元素
                root = null;
            } else {
                // 如果当前节点有右子树并且没有被访问, 要先去访问右子树, 保持左右中的顺序
                // 那么将当前节点压栈，指针指向右子树, 之后回溯的时候, 再去访问当前节点
                // 重复压栈以记录当前路径分叉节点
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }

}
